#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include "random.h"

/* The list element doubles as the list header as well. For the header
 * the next points to the first element, the prev points to the last
 * element and the record points to itself */
typedef struct listelem
{
  struct listelem * next_listelem;
  struct listelem * prev_listelem;
  void * record_listelem;
} listelem;

void * list_alloc(void)
{
  listelem * list;
  list = (listelem *)malloc(sizeof(listelem));
  list->next_listelem = list->prev_listelem = list->record_listelem = list;
  
  return list;
}

void list_free(void * list)
{
  #define LIST ((listelem *) list)
  listelem * first;

  first = LIST->next_listelem;
  
  while(first->record_listelem != first)
  {
    listelem * save = first;
    first = first->next_listelem;
    free(save);
  }
  
  free(LIST);
  #undef LIST
}

void list_insert_front(void * list, void * record)
{
  #define LIST ((listelem *) list)
  listelem * elem;

  /* allocate and initialize a new element */
  elem = (listelem *)malloc(sizeof(listelem));
  elem->record_listelem = record;

  elem->next_listelem = LIST->next_listelem;
  elem->prev_listelem = LIST;

  LIST->next_listelem->prev_listelem = elem;
  LIST->next_listelem = elem;

  #undef LIST
}

void list_insert_end(void * list, void * record)
{
  #define LIST ((listelem *) list)
  listelem * elem;

  /* allocate and initialize a new element */
  elem = (listelem *)malloc(sizeof(listelem));
  elem->record_listelem = record;

  elem->next_listelem = LIST;
  elem->prev_listelem = LIST->prev_listelem;

  LIST->prev_listelem->next_listelem = elem;
  LIST->prev_listelem = elem;

  #undef LIST
}

void * list_delete_front(void * list)
{
  #define LIST ((listelem *) list)
  void * record;
  listelem * first;
  
  first = LIST->next_listelem;

  if (first->record_listelem == first)
    return NULL;                             /* empty list */

  record = first->record_listelem; /* save the record for returning */
  
  LIST->next_listelem = first->next_listelem; /* move list forward */
  first->next_listelem->prev_listelem = LIST;
  
  free(first);                    /* release the memory of the elem */
  
  return record;
  
  #undef LIST
}

void * list_delete_end(void * list)
{
  #define LIST ((listelem *) list)
  void * record;
  listelem * last;
  
  last = LIST->prev_listelem;

  if (last->record_listelem == last)
    return NULL;                             /* empty list */

  record = last->record_listelem; /* save the record for returning */
  
  LIST->prev_listelem = last->prev_listelem;
  last->prev_listelem->next_listelem = LIST;
  
  free(last);                    /* release the memory of the elem */
  
  return record;
  
  #undef LIST
}

void list_delete_elem(void * elem)
{
  #define ELEM ((listelem *) elem)

  /* can't delete the list header !! */
  assert(ELEM->record_listelem != ELEM);
  
  ELEM->next_listelem->prev_listelem = ELEM->prev_listelem;
  ELEM->prev_listelem->next_listelem = ELEM->next_listelem;
  
  free(ELEM);                     /* release the memory of the elem */
  
  #undef ELEM
}

/* copies the records of list2 at the end of list1 and removes them
 * from list2 and frees list2
 */
void list_join(void * list1, void * list2)
{
  #define LIST1 ((listelem *) list1)
  #define LIST2 ((listelem *) list2)

  /* if the second list is empty, nothing to copy *
   * otherwise, attach the second list to the end of the first list */
  if (LIST2->next_listelem != LIST2)
  {
    LIST2->next_listelem->prev_listelem = LIST1->prev_listelem;
    LIST1->prev_listelem->next_listelem = LIST2->next_listelem;
    
    LIST2->prev_listelem->next_listelem = LIST1;
    LIST1->prev_listelem = LIST2->prev_listelem;
  }

  free(LIST2);
  
  #undef LIST1
  #undef LIST2
}

int list_count(void * list)
{
  #define LIST ((listelem *) list)
  int cnt;
  listelem * curr;
  
  cnt = 0;
  for(curr = LIST->next_listelem; curr->record_listelem != curr; 
      curr = curr->next_listelem)
    cnt ++;
  
  return cnt;
  
  #undef LIST
}

void * list_next(void * list)
{
  listelem * next = ((listelem *)list)->next_listelem;

  if (next != next->record_listelem)
    return next;
  else
    return NULL;
}

void * list_prev(void * list)
{
  listelem * prev = ((listelem *)list)->prev_listelem;

  if (prev != prev->record_listelem)
    return prev;
  else
    return NULL;
}

void * list_item(void * list)
{
  return ((listelem *)list)->record_listelem;
}

int list_is_empty(void * list)
{
  #define LIST ((listelem *) list)
  
  return LIST == LIST->next_listelem;
  
  #undef LIST
}

/***** SUGAR APIS ********/

/* returns NULL if no such element is found otherwise an iterator from
 * the element */
void * list_find(void * list, const void * record)
{
  void * iter;
  
  for (iter = list_next(list); iter; iter = list_next(iter))
  {
    if (list_item(iter) == record)
      return iter;
  }

  return iter;
}

/* returns an item at a specified index in the list, the index better
 * be less than the size of the list */
void * list_index(void * list, int index)
{
  void * iter;
  int pos;
  
  pos = 0;
  for (iter = list_next(list); iter; iter = list_next(iter))
  {
    if (pos == index)
      return list_item(iter);
    
    pos ++;
  }

  assert(0);                                 /* index out of range */
  return NULL;
}


/* add the record to the end of the list if not already in it */
void list_add(void * list, void * record)
{
  if (!list_find(list, record))
    list_insert_end(list, record);
}

void list_remove(void * list, const void * record)
{
  void * iter;
  
  for (iter = list_next(list); iter; iter = list_next(iter))
  {
    if (list_item(iter) == record)
      break;
  }

  assert(iter != NULL);
  
  list_delete_elem(iter);
}

/* remove a random record from the list */
void * list_remove_random(void * list)
{
  int n = list_count(list);
  int i;
  void * iter;
  void * ans;
  
  if (!n)
    return NULL;
  
  /* we will remove the nth element */
  n = (int) floor(((double) n) * RANDOM_DOUBLE);

  i = 0;
  for (iter = list_next(list); iter; iter = list_next(iter))
  {
    if (i == n)
      break;
    i ++;
  }

  assert(iter != NULL);
  
  ans = list_item(iter);

  list_delete_elem(iter);
  
  return ans;
}


/* get 1 item from a list of size 1 */
void list_item1(void * list, void ** ppitem1)
{
  list = list_next(list);
  *ppitem1 = list_item(list);
  
  assert(NULL == list_next(list));
}


/* get 2 items from a list of size 2 */
void list_item2(void * list, void ** ppitem1, void ** ppitem2)
{
  list = list_next(list);
  *ppitem1 = list_item(list);

  list = list_next(list);  
  *ppitem2 = list_item(list);
  
  assert(NULL == list_next(list));
}


/* get 3 items from a list of size 3 */
void list_item3(void * list, void ** ppitem1, void ** ppitem2,
                void  ** ppitem3)
{
  list = list_next(list);
  *ppitem1 = list_item(list);

  list = list_next(list);  
  *ppitem2 = list_item(list);

  list = list_next(list);  
  *ppitem3 = list_item(list);
  
  assert(NULL == list_next(list));
}

void * list_alloc1(void * record)
{
  void * list;
  
  list = list_alloc();
  list_insert_end(list, record);
  
  return list;
}

void * list_alloc2(void * record1, void * record2)
{
  void * list;

  list = list_alloc();
  list_insert_end(list, record1);
  list_insert_end(list, record2);
  
  return list;
}

void * list_alloc3(void * record1, void * record2, void * record3)
{
  void * list;

  list = list_alloc();
  list_insert_end(list, record1);
  list_insert_end(list, record2);
  list_insert_end(list, record3);
  
  return list;
}

